﻿using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.Drawing.Drawing2D;
using System.IO;
namespace MMDemo
{
    public partial class GraphsInputForm : Form
    {
        private const int VERTEXSIZE = 48;
        /// <summary>
        /// 图结点的最大数
        /// </summary>
        private const int MAX_NUM = 9;
        /// <summary>
        /// 图的结点数
        /// </summary>
        private int num = 0;
        /// <summary>
        /// 图的矩阵
        /// </summary>
        private int[,] GraphsMatrix;
        /// <summary>
        /// 结点图片
        /// </summary>
        private Bitmap NodeBmp = null;
        /// <summary>
        /// 圆的半径
        /// </summary>
        private int radius = 0;
        //保存线两端的结点索引
        private List<LineSideVertex> lineSideVertex = new List<LineSideVertex>();
        //保存按下鼠标是否在结点区域
        private bool IsMouseDowInNode = false;
        /// <summary>
        /// 保存鼠标移动的坐标
        /// </summary>
        private Point mouseMovePt = new Point();
        /// <summary>
        /// 保存鼠标按下去时的结点
        /// </summary>
        private int mouseDownNode = -1;
        private List<int> vertexs = new List<int>();
        /// <summary>
        /// 是否是有效的初始化
        /// </summary>
        public bool IsValuesInit = true;
        public GraphsInputForm()
        {
            InitializeComponent();
            String path = Application.StartupPath;
            NodeBmp = (Bitmap)Image.FromFile(path + "/image/node_nine.png");
            SetGraphsType();
        }
        private void SetGraphsType()
        {
            if (GlobalGraphs.OperatType == GraphsOperateType.Prim || GlobalGraphs.OperatType == GraphsOperateType.Kruskal)
            {
                SetCheckBox(true, false, false, false);
            }
            else if (GlobalGraphs.OperatType == GraphsOperateType.BFT || GlobalGraphs.OperatType == GraphsOperateType.DFT)
            {
                SetCheckBox(true, true, true, false);
            }
            else if(GlobalGraphs.OperatType == GraphsOperateType.TopologicalSortCheckLoop || GlobalGraphs.OperatType == GraphsOperateType.DFTCheckLoop)
            {
                SetCheckBox(false, false, true, false);
            }
            else if (GlobalGraphs.OperatType == GraphsOperateType.Dijkstra || GlobalGraphs.OperatType == GraphsOperateType.Bellman_Ford)
            {
                SetCheckBox(false, false, false, false);
            }
        }
        private void SetCheckBox(bool UnD_Check, bool UnD_Enabled, bool UnT_Check, bool UnT_Enabled)
        {
                UnDirectCheckBox.Checked = UnD_Check;
                UnDirectCheckBox.Enabled = UnD_Enabled;
                UnTitleCheckBox.Checked = UnT_Check;
                UnTitleCheckBox.Enabled = UnT_Enabled;
        }
        private void RandBtn_Click(object sender, EventArgs e)
        {
            RandCreateGraphs();
            this.GraphShowPictrueBox.Refresh();
        }
        /// <summary>
        /// 求n的排列
        /// </summary>
        private int An(int n)
        {
            int sum = 1;
            for(int i = 1; i <=n; ++i)
            {
                sum *= i;
            }
            return sum;
        }
        /// <summary>
        /// 求组合
        /// </summary>
        private int Cmn(int m, int n)
        {
            return An(n) / (An(m) * An(n - m));
        }
        private void CreateNodeBtn_Click(object sender, EventArgs e)
        {
            GraphsValueForm vertexForm = new GraphsValueForm();
            vertexForm.ChangeLabelText("顶点数:");
            vertexForm.ChangeTextValue("5");
            vertexForm.ShowDialog();
            try
            {
                num = Convert.ToInt32(vertexForm.GetTextValue());
                if (num > 9)
                {
                    num = 9;
                    MessageBox.Show("结点数最大为9，结束数将设置为9");
                }
            }
            catch
            {
                return;
            }
            vertexForm.Close();
            lineSideVertex.Clear();
            this.GraphShowPictrueBox.Refresh();
        }
        /// <summary>
        /// 随机生成图
        /// </summary>
        private void RandCreateGraphs()
        {
            Random rand = new Random();
            //随机生成图的结点数(1~9)
            num = rand.Next(MAX_NUM) + 1;
            //生成num*num矩阵
            GraphsMatrix = new int[num, num];
            //随机生成连线个数
            int lineNum = num  - 1 + num - 2;
            //随机生成lineNum条线
            int nodeOne, nodeTwo;
            lineSideVertex.Clear();
            if (!UnTitleCheckBox.Checked)
            {
                GraphShowPictrueBox.Refresh();
            }
            LineSideVertex tempLSN = new LineSideVertex();
            for (int i = 0; i < lineNum; ++i)
            {
                //随机连线的第一个结点
                nodeOne = rand.Next(num);
                //随机生成连线的第二个结点
                nodeTwo = rand.Next(num);
                //如果两个结点相同，就无连线吗
                if(nodeOne != nodeTwo)
                {
                            if (GraphsMatrix[nodeOne, nodeTwo] == 0)
                            {
                                int cost = 1;
                                if (!UnTitleCheckBox.Checked)
                                {
                                    cost = rand.Next(99) + 1;
                                }
                                if (UnDirectCheckBox.Checked)//如果是无向图的话
                                {
                                    GraphsMatrix[nodeOne, nodeTwo] = cost;
                                    GraphsMatrix[nodeTwo, nodeOne] = cost;
                                    int temp = 0;
                                    temp = nodeOne;
                                    //把小的顶点放在前面
                                    if (nodeOne > nodeTwo)
                                    {
                                        nodeOne = nodeTwo;
                                        nodeTwo = temp;
                                    }
                                }
                                else
                                {
                                    //如果有向图的话，矩阵对称的值不一样
                                    GraphsMatrix[nodeOne, nodeTwo] = cost;
                                }
                                tempLSN.SetValues(nodeOne, nodeTwo, cost);
                                lineSideVertex.Add(tempLSN);
                                GraphShowPictrueBox.Refresh();
                            }
                }
            }
        }

        private void GraphShowPictrueBox_Paint(object sender, PaintEventArgs e)
        {
            e.Graphics.SmoothingMode = SmoothingMode.HighQuality;
            if(IsMouseDowInNode)
            {
                Point downPt = GetNodePoint(mouseDownNode);
                e.Graphics.DrawLine(new Pen(Color.Red), downPt.X + VERTEXSIZE / 2, downPt.Y + VERTEXSIZE / 2,
                    mouseMovePt.X, mouseMovePt.Y);
            }
            ShowGraphs(e.Graphics);
        }
        private int GetCost()
        {
            GraphsValueForm costForm = new GraphsValueForm();
            costForm.ChangeLabelText("权值：");
            costForm.ChangeTextValue("1");
            costForm.ShowDialog();
            int cost = 0;
            try
            {
                cost = Convert.ToInt32(costForm.GetTextValue());
                if (cost >= 100)
                {
                    cost = 99;
                    MessageBox.Show("权值已经超过最大值，将会设置权值的值为最大值99");
                }
                else    if (cost < 0)
                {
                    if (GlobalGraphs.OperatType == GraphsOperateType.Dijkstra)
                    {
                        cost = -cost;
                        MessageBox.Show("Dijkstra算法权值不能负数，将会设置权值的绝对值");
                    }
                    else if (GlobalGraphs.OperatType == GraphsOperateType.Bellman_Ford)
                    {
                        if (cost < -99)
                        {
                            cost = -99;
                            MessageBox.Show("权值已经小于最小值，将会设置权值的值为最小值-99");
                        }
                    }
                }
                costForm.Close();
            }
            catch
            {
                MessageBox.Show("请输入数字！");
            }
            return cost;
        }
        private void OKBtn_Click(object sender, EventArgs e)
        {
            if(0 == num)
            {
                MessageBox.Show("图没有生成，请继续生成！");
                return;
            }
            if (!IsConnect())
            {
                MessageBox.Show("图不是连通的，请输入连通的图！");
                return;
            }
            PublicDataClass.IsInit = true;
            GlobalGraphs.VertexNum = num;
            GlobalGraphs.UnDirect = UnDirectCheckBox.Checked;
            GlobalGraphs.UnCost = UnTitleCheckBox.Checked;
            GlobalGraphs.LSN.Clear();
            lineSideVertex.Sort(new VertexComparer());
            lineSideVertex.ForEach(i => GlobalGraphs.LSN.Add(i));
            this.Close();
        } 
        private void ShowGraphs(Graphics g)
        {
            //起始角度
            double degrees = 180.0;
            //圆的半径
            radius = GetCircleRadius(GraphShowPictrueBox.Width, GraphShowPictrueBox.Height);
            //圆的中心坐标
            Point centerPt = new Point(GraphShowPictrueBox.Width / 2, GraphShowPictrueBox.Height / 2 - VERTEXSIZE / 2);

            Point startPt = new Point();
            Point endPt = new Point();
            //画线
            for (int i = 0; i < lineSideVertex.Count; ++i)
            {
                startPt = GetNodePoint(lineSideVertex[i].vertex_one);
                startPt.X += VERTEXSIZE / 2;
                startPt.Y += VERTEXSIZE / 2;
                endPt = GetNodePoint(lineSideVertex[i].vertex_two);
                endPt.X += VERTEXSIZE / 2;
                endPt.Y += VERTEXSIZE / 2;
                Pen p = new Pen(Color.Blue, 2);
                if (!UnDirectCheckBox.Checked)
                {
                    AdjustableArrowCap lineCap = new AdjustableArrowCap(6, 6);
                    p.CustomEndCap = lineCap;
                    endPt = SetArrowPoint(startPt, endPt);
                }
                
                g.DrawLine(p, startPt.X , startPt.Y, endPt.X, endPt.Y);
                if(!UnTitleCheckBox.Checked)//有权图
                {
                    int lineStart = (startPt.X + endPt.X) / 2;
                    int lineEnd = (startPt.Y + endPt.Y) / 2;
                    g.DrawString(lineSideVertex[i].cost.ToString(), new Font("微软雅黑", 10), Brushes.Red, lineStart, lineEnd);
                }
            }
            //根据图的结点数和圆画正几边形
            int x, y;
            double angle;
            double offsetDegrees = 360.0 / num;
            for (int i = 0; i < num; ++i)
            {
                angle = GetAngle(degrees);
                x = centerPt.X + (int)(radius * Math.Cos(angle));
                y = centerPt.Y + (int)(radius * Math.Sin(angle));
                g.DrawImage(NodeBmp, x, y, VERTEXSIZE, VERTEXSIZE);
                g.DrawString(i.ToString(), new Font("微软雅黑", 15), Brushes.White, x + VERTEXSIZE / 4, y + VERTEXSIZE / 4);
                degrees += offsetDegrees;
            }
       
        }
        /// <summary>
        /// 得到圆的半径
        /// </summary>
        private int  GetCircleRadius(int Width, int Height)
        {
            int  radius = 0;
            //圆的直径
            int diaMeter = Width > Height ? Height : Width;
            radius = diaMeter / 2 - 32;
            return radius;
        }
        private double GetAngle(double degrees)
        {
            return Math.PI * degrees / 180.0;
        }
        /// <summary>
        /// 根据第几个结点得到结点的坐标
        /// </summary>
        private Point GetNodePoint(int n)
        {
            double degrees = 180.0 + n * 360 / num;
            double angle = GetAngle(degrees);
            Point nodePt = new Point();
            nodePt.X = GraphShowPictrueBox.Width / 2 + (int)(radius * Math.Cos(angle));
            nodePt.Y = GraphShowPictrueBox.Height / 2 - VERTEXSIZE / 2 + (int)(radius * Math.Sin(angle));
            return nodePt;
        }

        private void GraphShowPictrueBox_MouseDown(object sender, MouseEventArgs e)
        {
            mouseDownNode = IsInVertexRect(e.X, e.Y);
            if(mouseDownNode != -1)
            {
                IsMouseDowInNode = true;
                mouseMovePt.X = e.X;
                mouseMovePt.Y = e.Y;
            }
        }

        private void GraphShowPictrueBox_MouseMove(object sender, MouseEventArgs e)
        {
            if(IsMouseDowInNode &&(e.X != mouseMovePt.X || e.Y != mouseMovePt.Y))
            {
                mouseMovePt.X = e.X;
                mouseMovePt.Y = e.Y;
                GraphShowPictrueBox.Refresh();
            }
        }

        private void GraphShowPictrueBox_MouseUp(object sender, MouseEventArgs e)
        {
            if(IsMouseDowInNode)
            {
                IsMouseDowInNode = false;
                int node = IsInVertexRect(e.X, e.Y);
                if(node != mouseDownNode && node != -1)
                {
                    LineSideVertex LSN = new LineSideVertex();
                    if (UnDirectCheckBox.Checked)
                    {
                        int temp = mouseDownNode;
                        if (mouseDownNode > node)
                        {
                            mouseDownNode = node;
                            node = temp;
                        }
                    }
                    LSN.vertex_one = mouseDownNode;
                    LSN.vertex_two = node;
                    LSN.cost = 1;
                    if (!FindSideExist(mouseDownNode, node))
                    {
                        if (!UnTitleCheckBox.Checked)
                        {
                            LSN.cost = GetCost();
                        }
                        lineSideVertex.Add(LSN);
                    }
                    else
                    {
                        MessageBox.Show("邻接边已经存在！");
                    }
                } 
                GraphShowPictrueBox.Refresh();
            }
        }
        /// <summary>
        /// 坐标是否在顶点上
        /// </summary>
        private int IsInVertexRect(int x, int y)
        {
            Point vertexPt = new Point();
            for (int i = 0; i < num; ++i)
            {
                vertexPt = GetNodePoint(i);
                if (x >= vertexPt.X && x <= vertexPt.X + VERTEXSIZE
                    && y >= vertexPt.Y && y <= vertexPt.Y + VERTEXSIZE)
                {
                    return i;
                }
            }
                return -1;
        }
        private bool FindSideExist(int vertexOne, int vertexTwo)
        {
            for (int i = 0; i < lineSideVertex.Count; ++i)
            {
                if (UnDirectCheckBox.Checked)
                {
                    if (lineSideVertex[i].vertex_one == vertexOne && lineSideVertex[i].vertex_two == vertexTwo
                        || lineSideVertex[i].vertex_one == vertexTwo && lineSideVertex[i].vertex_two == vertexOne)
                    {
                        return true;
                    }
                }
                else
                {
                    if (lineSideVertex[i].vertex_one == vertexOne && lineSideVertex[i].vertex_two == vertexTwo)
                    {
                       return true;
                    }
                }
            }
            return false;
        }
        private bool FindVertexExsit(int n)
        {
            for (int i = 0; i < vertexs.Count; ++i)
            {
                if (n == vertexs[i])
                {
                    return true;
                }
            }
            return false;
        }
        /// <summary>
        /// 判断是否是连通
        /// </summary>
        /// <returns></returns>
        private bool IsConnect()
        {
            vertexs.Clear();
            vertexs.Add(0);
            int index = 0;
            for(int i = index; i < vertexs.Count; ++i)
            {
                for (int j = 0; j < lineSideVertex.Count; ++j)
                {
                    int tempVertex = -1;
                    if (vertexs[i] == lineSideVertex[j].vertex_one)
                    {
                        tempVertex = lineSideVertex[j].vertex_two;
                    }
                    else if (vertexs[i] == lineSideVertex[j].vertex_two)
                    {
                        tempVertex = lineSideVertex[j].vertex_one;
                    }
                    if (tempVertex != -1)
                    {
                        if (!FindVertexExsit(tempVertex))
                        {
                            vertexs.Add(tempVertex);
                        }
                    }
                }
                if (vertexs.Count == 1)
                {
                    return false;
                }
                ++index;
            }
            if (vertexs.Count < num)
            {
                return false;
            }
            return true;
        }
        /// <summary>
        /// 求箭头的坐标
        /// </summary>
        private Point SetArrowPoint(Point StartPt, Point EndPt)
        {
            Point ArrowPt = EndPt;
            int OffsetX = 0, OffsetY = 0;
            int Width = EndPt.X - StartPt.X;
            int Height = EndPt.Y - StartPt.Y;
            //对角线的长度
            int diagonal = (int)Math.Sqrt(Width*Width + Height*Height);
            int r = VERTEXSIZE / 2;
            OffsetX = -  r * Width / diagonal;
            OffsetY = -  r * Height / diagonal;
            ArrowPt.X += OffsetX;
            ArrowPt.Y += OffsetY;
            return ArrowPt;
        }
        protected override void WndProc(ref   Message m)
        {
            const int WM_SYSCOMMAND = 0x0112;
            const int SC_CLOSE = 0xF060;
            if (m.Msg == WM_SYSCOMMAND && (int)m.WParam == SC_CLOSE)
            {
                PublicDataClass.IsInit = false;
                this.Close();
                return;
            }
            base.WndProc(ref m);
        }

        private void FileBtn_Click(object sender, EventArgs e)
        {
            ReadGraphFormFile();
            this.GraphShowPictrueBox.Refresh();
        }
        private void ReadGraphFormFile()
        {
            bool IsReadSucceed = true;
            string file_path = "";
            OpenFileDialog fileDialog = new OpenFileDialog();
            fileDialog.Filter = "*.txt|*.*";
            if (fileDialog.ShowDialog() == DialogResult.OK)
            {
                file_path = fileDialog.FileName;
                StreamReader read = new StreamReader(file_path);
                string str = "";
                while ((str = read.ReadLine()) != null)
                {
                    if (!ReadMaxtrix(str))
                    {
                        lineSideVertex.Clear();
                        IsReadSucceed = false;
                        break; ;
                    }
                }
            }
            if (!IsReadSucceed)
            {
                MessageBox.Show("文件格式不正确,每行的格式应为[v1,v2] = cost。其中v1,v2为数字顶点，cost为权值");
            }
        }
        private bool ReadDirectOrTitle(string direct)
        {
            if (direct == null)
            {
                return false;
            }
            string[] data = direct.Split('=');
            if (data.Length != 2)
            {
                return false;
            }
            if (data[0].Trim().ToLower() != "direct" || data[0].Trim().ToLower() != "title")
            {
                return false;
            }
            string strbool = data[1].Trim().ToLower();
            if (strbool != "true" || strbool != "false")
            {
                return false;
            }
            else
            {
                if (strbool == "true")
                {
                    if (data[0].Trim().ToLower() != "direct")
                    {
                        UnDirectCheckBox.Checked = false;
                    }
                    else
                    {
                        UnTitleCheckBox.Checked = false;
                    }
                }
                else
                {
                    if (data[0].Trim().ToLower() != "title")
                    {
                        GlobalGraphs.UnDirect = false;
                    }
                    else
                    {
                        GlobalGraphs.UnCost = false;
                    }
                }
                return true;
            }
        }
        private bool ReadMaxtrix(string maxtrix)
        {
            int vertex_one = -1;
            int vertex_two = -1;
            int cost = 0;
            string[] data = maxtrix.Split('=');
            if (data.Length != 2)
            {
                return false;
            }
            try
            {
                cost = Convert.ToInt32(data[1].Trim());
                if (cost > 99)
                {
                    cost = 99;
                }
            }
            catch
            {
                return false;
            }
            data[0] = data[0].Trim();
            if (data[0][0] != '[' || data[0][data[0].Length - 1] != ']')
            {
                return false;
            }
            int index = data[0].IndexOf(',');
            try
            {
                string str_vertex = data[0].Substring(1, 1).Trim();
                vertex_one = Convert.ToInt32(str_vertex);
                if (vertex_one < 0)
                {
                    return false;
                }
                str_vertex = data[0].Substring(index + 1, 1).Trim();
                vertex_two = Convert.ToInt32(str_vertex);
            }
            catch
            {
                return false;
            }
            int temp = vertex_one > vertex_two ? vertex_one : vertex_two + 1;
            if (temp > num)
            {
                num = temp;
            }
            if (num > 9 || vertex_one < 0 || vertex_two < 0)
            {
                num = 0;
                return false;
            }
            lineSideVertex.Add(new LineSideVertex(vertex_one, vertex_two, cost));
            return true;
        }

        private void UnDirectCheckBox_CheckedChanged(object sender, EventArgs e)
        {
            GraphShowPictrueBox.Refresh();
        }
    }
}
